package binary_tree.searchtree;

import java.util.NoSuchElementException;

/**
 * @Description: 二叉搜索树的实现
 * @Author Stark
 * @Date 2022/3/12 19:10
 **/
public class BST {
    private class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode head;
    private int size;

    /**
    * @Description: 添加元素
    * @Param: [val]
    * @return: void
    */
    public void add(int val) {
        head = add(head, val);
        size++;
    }

    private TreeNode add(TreeNode head, int val) {
        if (head == null) {
            return new TreeNode(val);
        }
        if (head.val < val) {
            head.right = add(head.right, val);
        }
        if (head.val > val) {
            head.left = add(head.left, val);
        }
        return head;
    }

    /**
    * @Description: 判断结点是否存在
    * @Param: [val]
    * @return: boolean
    */
    public boolean contains(int val) {
        return contains(head, val);
    }

    private boolean contains(TreeNode head, int val) {
        if (head == null) {
            return false;
        }
        if (head.val == val) {
            return true;
        } else if (head.val < val) {
            return contains(head.left, val);
        } else {
            return contains(head.right, val);
        }
    }

    public int size(){
        return size;
    }

    /**
    * @Description: 找最小的结点
    * @Param: []
    * @return: int
    */
    public int findMin(){
        if(head == null){
            throw new NoSuchElementException("BST is empty! Can't find min");
        }
        TreeNode node = findMin(head);
        return node.val;
    }

    //返回的是最小结点的索引
    private TreeNode findMin(TreeNode head) {
        if(head.left == null){
            return head;
        }
        return findMin(head.left);
    }
    
    /**
    * @Description: 找BST的最大值
    * @Param: [] 
    * @return: int 
    */ 
    public int findMax(){
        if(head == null){
            throw new NoSuchElementException("BST is empty! Can't find max");
        }
        TreeNode node = findMax(head);
        return node.val;
    }

    private TreeNode findMax(TreeNode head) {
        if(head.right == null){
            return head;
        }
        return findMax(head.right);
    }

    /**
    * @Description: 删除最小的结点
    * @Param: []
    * @return: int
    */
    public int removeMin(){
        int min = findMin();
        removeMin(head);
        return min;
    }

    //返回的删除最小结点后的头结点
    private TreeNode removeMin(TreeNode head) {
        if(head.left == null){
            TreeNode tmp = head.right;
            //将结点完全脱离树,便于回收
            head.right = head = null;
            size--;
            return tmp;
        }
        head.left = removeMin(head.left);
        return head;
    }

    /**
    * @Description: 删除最大的结点
    * @Param: []
    * @return: int
    */
    public int removeMax() {
        int max = findMax();
        removeMax(head);
        return max;
    }

    private TreeNode removeMax(TreeNode head) {
        if(head.right == null){
            TreeNode tmp = head.left;
            head.right = head = null;
            size--;
            return tmp;
        }
        head.right = removeMax(head.right);
        return head;
    }
    
    /**
    * @Description: 删除任意结点
    * @Param: [val] 
    * @return: void 
    */ 
    public void remove(int val){
        remove(head,val);
    }

    private TreeNode remove(TreeNode head,int val) {
        if(head == null){
            throw new NoSuchElementException("Doesn't exist this node!");
        }else if(val > head.val){
            head.right = remove(head.right,val);
            return head;
        }else if(val < head.val){
            head.left = remove(head.left,val);
            return head;
        }else{
            if(head.left == null){
                TreeNode node = head.right;
                head.right = head = null;
                size--;
                return node;
            }
            if(head.right == null){
                TreeNode node = head.left;
                head.left = head = null;
                size--;
                return node;
            }
            //左右子树都不为空
            TreeNode node = findMin(head.right);
            node.right = removeMin(head.right);
            node.left = head.left;
            head.left = head.right = head = null;
            return node;
        }
    }

    /**
    * @Description: 打印BST
    * @Param: []
    */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        toStringHelper(head, 0,sb);
        return sb.toString();
    }

    private void toStringHelper(TreeNode head, int height,StringBuilder sb) {
        if(head == null){
            sb.append(countHeight(height)).append("NULL\n");
            return;
        }
        sb.append(countHeight(height)).append(head.val).append('\n');
        toStringHelper(head.left,height + 1,sb);
        toStringHelper(head.right,height + 1,sb);
    }

    private String countHeight(int height) {
        String str = "";
        while(height > 0){
            str += "--";
            height--;
        }
        return str;
    }
}
